A conventional RFID tag typically comprises an integrated circuit transceiver capable of transmitting a unique serial number or other identifier to a nearby reader in response to a query from the reader.
An example of an inexpensive RFID tag providing such basic functionality is described in S. E. Sarma, “Towards the five-cent tag,” Technical Report MIT-AUTOID-WH-006, MIT Auto ID Center, 2001. This RFID tag transmits a static, 64-to-128-bit identifier on receiving a reader query.
An example of a more advanced RFID tag is the TK5552 transponder, commercially available from Atmel Corporation, of San Jose, Calif., U.S.A. This tag provides a small user-programmable memory, with a storage capacity on the order of about 1000 bits, as well as other enhanced functionality relative to the more basic RFID tag previously described, but at a substantially higher cost.
It is expected that ongoing RFID tag development efforts will continue to produce cost and size reductions, which should result in a rapid proliferation of RFID tags into many new areas of use. The impending ubiquity of RFID tags, however, poses a potentially widespread threat to consumer privacy. The simplest conventional RFID tag will typically broadcast its unique identifying information to any nearby reader. The movements of a given consumer or other user can therefore be readily tracked by simply monitoring the RFID tags in goods carried by or otherwise associated with that user. The above-cited U.S. patent application Ser. No. 10/673,540 discloses techniques for selective blocking of RFID tags, in a manner that protects consumer privacy.
Another significant problem that can arise in conventional RFID tags of the type described above is that such tags can be difficult to authenticate. For example, these and other RFID tags may be easily cloned by an attacker that has read access, since as previously noted the tags typically broadcast their identifiers in a promiscuous manner to any nearby readers.
As is well known, there are numerous cryptographic techniques that are capable of providing secure authentication between properly-equipped devices. However, such techniques generally require substantial computational and storage resources, well beyond those associated with even an advanced RFID tag such as the above-described Atmel TK5552 transponder. Conventional cryptographic techniques are thus generally far too complex to implement within the limited computational and storage capabilities typical of existing RFID tags.
Accordingly, a need exists for improved cryptographic techniques that solve the above-identified authentication problem without requiring a significant increase in the computational and storage resources, and thus the cost, of the RFID tags.